package leetcode;

public class Solution105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd){
        System.out.println("preStart-----" + preStart + ", preEnd------" + preEnd + ", inStart------" + inStart + ", inEnd-----" + inEnd);
        if(preStart > preEnd){return null;}
        TreeNode node = new TreeNode(0);
        // 找到前序数组中的根节点
        int val = preorder[preStart];
        node.val = val;
        // 找到中序数组中的根节点
        int index = -1;
        for(int i = 0; i <= inEnd; i++){
            if(val == inorder[i]){
                index = i;
                break;
            }
        }
        node.left = buildTree(preorder, preStart + 1, preStart + index - inStart,
                inorder, inStart, index);

        node.right = buildTree(preorder, preStart + index - inStart + 1, preEnd,
                inorder, index + 1, inEnd);
        return node;
    }

    public static void main(String[] args) {
        int[] preorder = {3,8,9,6,20,15,7};
        int[] inorder = {9,8,6,3,15,20,7};
        System.out.println(new Solution105().buildTree(preorder, inorder));
    }
}
